# -*- coding: utf-8 -*-
# 给定一个 n × n 的二维矩阵表示一个图像
# 将图像顺时针旋转 90 度
# 说明：
# 你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像

# 示例 1:
# 给定 matrix = 
# [
#   [1,2,3],
#   [4,5,6],
#   [7,8,9]
# ],
# 原地旋转输入矩阵，使其变为:
# [
#   [7,4,1],
#   [8,5,2],
#   [9,6,3]
# ]

# 示例 2:
# 给定 matrix =
# [
#   [ 5, 1, 9,11],
#   [ 2, 4, 8,10],
#   [13, 3, 6, 7],
#   [15,14,12,16]
# ], 
# 原地旋转输入矩阵，使其变为:
# [
#   [15,13, 2, 5],
#   [14, 3, 4, 1],
#   [12, 6, 8, 9],
#   [16, 7,10,11]
# ]

# # 理解题目错误，以为是不让直接使用matrix的库，实际上是不让使用额外的空间
# class Solution(object):
#     def rotate(self, matrix):
#         """
#         :type matrix: List[List[int]]
#         :rtype: None Do not return anything, modify matrix in-place instead.
#         """
#         length = len(matrix);
#         rtn = [[0] * length for i in xrange(0, length)];

#         for i in xrange(0, length):
#             row = matrix[i];
#             col = length - 1 - i;
#             for j in xrange(0, length):
#                 rtn[j][col] = row[j];

#         for i in xrange(0, length):
#             for j in xrange(0, length):
#                 matrix[i][j] = rtn[i][j];



# # 剥洋葱 一圈一圈的处理
# # 解题思路：
# # 处理以下矩阵
# # 1   2   3   4
# # 5   6   7   8
# # 9   10  11  12
# # 13  14  15  16
# # 
# # 顺时针旋转矩阵即把
# # 第1行 转换为 倒数第1列
# # 第2行 转换为 倒数第2列
# # ....
# # 
# # 1、选中[0,0] pick = 1
# #[?]  2   3   4
# # 5   6   7   8
# # 9   10  11  12
# # 13  14  15  16
# # 通过上面的计算可知，需要把它放置在[0,3] pick = 4
# # ?  2   3  [1]
# # 5   6   7   8
# # 9   10  11  12
# # 13  14  15  16
# # 2、因为[0,3]被占用了，因而我们需要找到[0,3]需要放置的位置，通过计算可得[3,3] pick = 16
# # ?   2   3   1
# # 5   6   7   8
# # 9   10  11  12
# # 13  14  15 [4]
# # 3、[3,3]也需要放置 计算可得[3,0] pock = 13
# # ?   2   3   1
# # 5   6   7   8
# # 9   10  11  12
# #[16] 14  15  4
# #4、[3,0]也需要放置 计算可得[0,0]
# # 13  2   3   1
# # 5   6   7   8
# # 9   10  11  12
# # 16  14  15  4
# # 
# #5、通过#1 #2 #3 #4我们完成了一个元素的移动
# # 同理我们可以移动[0,1] [0,2]
# # 移动完成后
# # 13  9   5   1
# # 14 [6   7 ] 2
# # 15 [10  11] 3
# # 16  12  8   4
# # 
# # 可以看到外围的一圈已经完成了移动
# # 同理里面的一圈也可以通过以上#1、#2、#3、#4、#5进行完成，这样一圈一圈直到完全剥完
# class Solution(object):
#     def rotate(self, matrix):
#         """
#         :type matrix: List[List[int]]
#         :rtype: None Do not return anything, modify matrix in-place instead.
#         """
#         length = len(matrix);
#         onion = 0;

#         while length - 2 * onion - 1 > 0:
#             for i in xrange(0,  length - 2 * onion - 1):
#                 index = onion * length + onion + i;
#                 row = index // length;
#                 col = index % length;

#                 pick = matrix[row][col];
#                 next_row = col;
#                 next_col = length - 1 - row;

#                 while True:
#                     matrix[next_row][next_col], pick = pick, matrix[next_row][next_col];

#                     if next_row * length + next_col == index:
#                         break;

#                     next_row, next_col = next_col, length - 1 - next_row;

#             onion += 1;

#         print matrix;


# # 阅读官方的解决方案，上面剥洋葱方案的更好的书写方式
# class Solution(object):
#     def rotate(self, matrix):
#         """
#         :type matrix: List[List[int]]
#         :rtype: None Do not return anything, modify matrix in-place instead.
#         """
#         length = len(matrix);
#         # 洋葱的圈数可以通关计算获得，而不必使用while循环
#         for i in range(length // 2 + length % 2):
#             # 每一圈的起点[i,i]长度为length - 1 - i * 2
#             for j in range(length - 1 - i * 2):
#                 # 针对每一个元素，旋转4次构成一次操作
#                 row, col = i, i + j;
#                 pick = matrix[row][col];
#                 for k in range(4):
#                     row, col = col, length - 1 - row;
#                     matrix[row][col], pick = pick, matrix[row][col];

#         print matrix;










# 更容易理解记忆的解决方案 转置 + 行反转
class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        length = len(matrix);
        for i in range(length):
            for j in range(i, length):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j];

        # for i in range(length):
        #     for j in range(0, length // 2):
        #         matrix[i][j], matrix[i][length - 1 - j] = matrix[i][length - 1 - j], matrix[i][j];

        for i in range(length):
            matrix[i].reverse();

        print matrix;




t = Solution();
t.rotate([[1,2,3],[4,5,6],[7,8,9]]);